返回

转到题目

题目思路

我们想最大化这个整体

思路1:

首先，我们每一步增益操作是什么?

• 每当 num[i-1] < num[i] - 1 时能保证操作是正向增益的
• 那怎么找到整体最优呢?
• 每一步操作都是会影响到 num[i] 的 基准
  • 也就是说，你只能找到单一维度的最优解.这种贪心是会遗漏最优解的.
  • 为了找到全局最优，我们需要回退，回退最少9步，这样定能找到全局最优
  • 模拟回退机制

    思路2:

    我最大化结果，那我贪心的话，贪心数位 我们知道，不管哪个数位先确定，都会影响到后面的数位(削减)，所以我们可以贪心确定每一位。

• 首先，我们先确定第一位(当前增益最大)，也就是 num[0]
  • 我们枚举可能对此为有增益的所有数位,也就是后9位，选最大值。
  • 选完后将修改原数据，贪心确定第一位。然后确定第二位(当前增益最大)，以此类推。
• 如此依次选择，贪心先让最大权位确定,能保证在有限操作下，保证当前最优结果